package main

import "fmt"

type MonotonicQueue struct {
	maxQueue []int
}

func Constructor(lenth int) MonotonicQueue {
	return MonotonicQueue{
		maxQueue: make([]int, 0, lenth),
	}
}

func (m *MonotonicQueue) Max() (max int, ok bool) {
	if len(m.maxQueue) == 0 {
		ok = false
		return
	}
	max = m.maxQueue[0]
	ok = true
	return
}

func (m *MonotonicQueue) Push(n int) {
	for {
		if len(m.maxQueue) > 0 && m.maxQueue[len(m.maxQueue)-1] < n {
			m.maxQueue = append(m.maxQueue[:len(m.maxQueue)-1], m.maxQueue[len(m.maxQueue):]...)
		} else {
			break
		}
	}
	m.maxQueue = append(m.maxQueue, n)
}

func (m *MonotonicQueue) Pop(n int) {
	if m.maxQueue[0] == n {
		m.maxQueue = m.maxQueue[1:len(m.maxQueue)]
	}
}

func maxSlidingWindow(nums []int, k int) []int {
	res := make([]int, 0, len(nums)-k+1)
	mq := Constructor(k + 1)

	for i := 0; i < len(nums); i++ {
		if i < k-1 {
			mq.Push(nums[i])
		} else {
			mq.Push(nums[i])
			if v, ok := mq.Max(); ok {
				res = append(res, v)
			}
			mq.Pop(nums[i-k+1])
		}
	}

	return res
}

func main() {
	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
	k := 3
	fmt.Println(maxSlidingWindow(nums, k))

}
